{--
The smallest number expressible as the sum of a prime square, 
prime cube, and prime fourth power is 28. 
In fact, there are exactly four numbers below fifty that can be expressed 
in such a way:

28 = 2² + 2³ + 2⁴
33 = 3² + 2³ + 2⁴
49 = 5² + 2³ + 2⁴
47 = 2² + 3³ + 2⁴

How many numbers below fifty million can be expressed as the sum of a prime 
square, prime cube, and prime fourth power?
-}

module examples.Euler87 where

-- import Data.Tuples
import Data.TreeMap
import examples.EulerLib
-- import frege.prelude.Floating

-- 1097343
-- runtime 19.485 wallclock seconds.
-- Level 3 Rank 355

limit = 50_000_000 

main _  = do
        -- sequence_ (map println sums)
        println (length (keys (fromKeys sums)))
    where
        sums = [ sum  |
                     p4 <- p4s, p3 <- p3s,
                     p3 + p4 < limit,
                     p2 <- takeWhile (< limit-p4-p3) p2s,
                     let !sum = p2+p3+p4                     
                 ] 
        sqr :: Int -> Int
        sqr n = n*n 
        sqr3 :: Int ->Int
        sqr3 n = n*n*n
        -- the list of prime fourth powers below the limit
        p4s = takeWhile (<limit) • map (sqr • sqr) $ primes
        p3s = takeWhile (<limit) • map sqr3 $ primes
        p2s = takeWhile (<limit) • map sqr  $ primes
        
        